package leetcodev1.树;

import leetcodev1.链表.Solution;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode100 {

    boolean ret = true;

    //以某种遍历顺序进行遍历
    //1.递归遍历
    public boolean isSameTree(TreeNode p, TreeNode q) {
        helper(p, q);
        return ret;
    }

    private void helper(TreeNode p, TreeNode q) {
        if (!ret) {
            return;
        }

        if (p == null && q == null) {
            return;
        }

        if (p != null && q != null) {
            if (p.val != q.val) {
                ret = false;
                return;
            }
            helper(p.left, q.left);
            helper(p.right, q.right);
            return;
        }
        ret = false;
    }
}

class Answer100 {
    //1.深度优先遍历 dfs优先遍历到最底层节点
    //2.广度优先遍历 bfs 优先横着遍历（层次遍历）

    //1.深度优先遍历
    //虽然很优雅..但是需要遍历完所有的数
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

    //2.广度优先遍历
    //层次遍历
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        //利用队列
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            //一个为空 另一个不为空不相同
            //可以关注下这种写法
            if (left1 == null ^ left2 == null) {
                return false;
            }
            //一个为空 另一个不为空不相同
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }

}
